package com.sx.sx1.lintcode.day717;

import java.util.HashMap;
import java.util.Map;

public class LC1087 {

    static class Solution {
        /**
         * @param edges: List[List[int]]
         * @return: return List[int]
         */
        public int[] findRedundantDirectedConnection(int[][] edges) {
            int n = edges.length;
            int[] in = new int[n+1];
            for (int[] edge : edges) {
                in[edge[1]]++;
            }

            //尝试删除度为2的边
            for (int i = n-1; i >=0 ; i--) {
                if(in[edges[i][1]] == 2) {
                    //删掉这条边如果形成的图无环
                    // 说明这条边就是要删除的，题目要求多个答案，留最后一个，因此从最后一个元素开始处理
                    if(!hasCircle(edges,i)){
                        return edges[i];
                    }
                }
            }

            //尝试删除度为1的边
            for (int i = n-1; i >=0 ; i--) {
                if(in[edges[i][1]] == 1) {
                    //删掉这条边如果形成的图无环
                    // 说明这条边就是要删除的，题目要求多个答案，留最后一个，因此从最后一个元素开始处理
                    if(!hasCircle(edges,i)){
                        return edges[i];
                    }
                }
            }

            return new int[]{0};
        }


        public boolean hasCircle(int[][] edges,int idx){

            UF uf = new Solution.UF();
            for (int i =0;i<edges.length;i++) {
                if(i == idx) continue;
                int[] edge = edges[i];
                int a = edge[0];
                int b = edge[1];

                int f1 = uf.find(a);
                int f2 = uf.find(b);

                if(f1 ==f2) return true;

                uf.union(f1,f2);
            }

            return false;
        }


        static class UF{  //并查集
            public Map<Integer,Integer> parents = new HashMap<>();
            public Map<Integer,Integer> size = new HashMap<>();
            public Map<Integer,Integer> help = new HashMap<>();
            public int sets = 0;

            public int find(int x){
                if(!parents.containsKey(x)){
                    parents.put(x,x);
                    size.put(x,1);
                    sets++;
                }

                int hi=0;
                while (x!=parents.get(x)){
                    help.put(hi++,x);
                    x= parents.get(x);
                }

                for(hi--;hi>=0;hi--){
                    parents.put(help.get(hi),x);
                }

                return x;
            }

            public  void union(int a,int b){
                int f1 = find(a);
                int f2 = find(b);

                if(f1!=f2){
                    int s1 = size.get(f1);
                    int s2= size.get(f2);
                    int sum =s1+s2;
                    if(s1>=s2){
                        size.put(f1,sum);
                        parents.put(f2,f1);
                    }else{
                        size.put(f2,sum);
                        parents.put(f1,f2);
                    }

                    sets--;
                }
            }
        }



    }

    public static void main(String[] args) {
        Solution s = new Solution();
        show(s.findRedundantDirectedConnection(new int[][]{{6,3},{8,4},{9,6},{3,2},{5,10},{10,7},{2,1},{7,6},{4,5},{1,8}}));


    }
    public static void show(int[] arr){
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
1087 · 冗余的连接 II
算法
困难
通过率
31%

题目
题解12
笔记
讨论17
排名
记录
描述
在这个问题中，有根树是一种这样的有向图，它只有一个根节点，所有其他节点都是该节点的后代，加上每个节点只有一个父母节点，（除了根节点没有父母）。

给定的输入是一个有向图，它以具有N个节点（具有不同的值1,2，...，N）的有根树开始，并添加了一个额外的有向边。 添加的边有两个不同的顶点，从1到N中选择，并且不是已经存在的边。

得到的图形以边的2D数组给出。 边的每个元素是一对[u，v]，表示连接节点u和v的有向边，其中u是子v的父节点。

返回可以删除的边，以便生成的图是N个节点的有根树。 如果有多个答案，则返回给定2D数组中最后出现的答案。

输入2D数组的大小将介于3和1000之间。
2D数组中表示的每个整数都在1和N之间，其中N是输入数组的大小。

样例
样例 1:

输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图将是这样的:
  1
 / \
v   v
2-->3
样例 2:

输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图将是这样的:
5 <- 1 -> 2
     ^    |
     |    v
     4 <- 3
标签
企业
Google
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
24/43
已开启智能提示
发起考试
45 分 00 秒
123456789


 */
